
/**
 * 
 * 补种未成活胡杨
 * 
 * 题目描述

近些年来，我国防沙治沙取得显著成果。

某沙漠新种植 N 棵胡杨（编号1-N），排成一排。一个月后，有 M 棵胡杨未能成活。

现可补种胡杨 K 棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？



输入描述
N 总种植数量

1 ≤ N ≤ 100000
M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列

1 ≤ M ≤ N
K 最多可以补种的数量，

0 ≤ K ≤ M
输出描述
最多的连续胡杨棵树

用例
输入	
5
2
2 4
1
输出	
3
说明	补种到2或4结果一样，最多的连续胡杨棵树都是3。
输入	10
3
2 4 7
1
输出	6
说明	补种第7棵树，最多连续胡杨树棵数位6（5，6，7，8，9，10）

 */

import java.util.Scanner;

/**
  * 
  题目解析
如下图中，红色数字表示死树的编号。

现在我们能够补种 K 棵树，即填充 K 个红色死树格子。

比如 k == 1 时，有如下填充方案，黄色+绿色部分就是连续的活的胡杨树区域。



比如 k == 2，则填充方案如下：



总树有 n 棵，死树有 m 棵，且死树编号保存在 dead 数组中，补种 k 棵。

比如dead = [2,5,8]，k = 2

如果我们从 dead[0] 开始补种的话，则可以补种 dead[0] 和 dead[1]，用完 k 棵树。
如果我们从 dead[1] 开始补种的话，则可以补种 dead[1] 和 dead[2]，用完 k 棵树。
如果我们从 dead[2] 开始补种的话，则可以只能补种 dead[2]，用不完 k 棵树。
因此 dead 数组补种起始位置范围是 [0, m - k]

下面

从 dead[0] 开始补种（向左可以包含开头编号1的胡杨树），此时连续胡杨树的
开始编号：1
结束编号：dead[0+k] - 1
长度：（dead[0+k] - 1）- 1 + 1


从dead[m-k] 开始补种（向右可以包含结尾编号为 n 的胡杨树），此时连续胡杨树的
开始编号：dead[m-k-1] + 1
结束编号：n
长度：n - (dead[m-k-1] + 1) + 1
 

如果从其余dead[i] 开始补种，此时连续胡杨树的：
开始编号：dead[i-1] + 1
结束编号：dead[i+k] - 1
长度：(dead[i + k] - 1) - (dead[i-1] + 1) + 1 


2023.09.09

上面逻辑应该考虑下m == k的情况，即补种数 == 未成活数，此时可以直接返回n，即补种后所有树都成活了。
  */

public class 补种未成活胡杨 {
    
    public static void main(String[] args) {
    
        try{

            Scanner scanner = new Scanner(System.in);

            //全部数
            int totalTreeCount = scanner.nextInt();
            //死亡的树
            int deadTreeCount = scanner.nextInt();

            //死亡树的下标数组
            int[] deadTreePositionArr = new int[deadTreeCount];
            for(int i=0; i<deadTreeCount; i++){
                deadTreePositionArr[i] = scanner.nextInt();
            }

            //补种数
            int saveCount = scanner.nextInt();


            if(saveCount == deadTreeCount){

                //全部补种
                System.out.println(totalTreeCount);
            } else {

                int maxLen = 0;
                //补种的范围 [0 deadTreeCount - saveCount]
                int positionMax = deadTreeCount-saveCount;
                for(int i=0; i<= positionMax; i++){

                    //因为种树的队列是连续的，1,2,3,4,5，6,7
                    //死树的队列    2， 3， 7
                    //如果补种1
                    if(0 == i){

                        //如果补种第一棵树
                        //长度  [0 ~ i+saveCount] -1 
                        maxLen = Math.max(maxLen, deadTreePositionArr[i + saveCount] - 1);

                    } else if(i == positionMax){

                        //如果补种最后棵树
                        //长度  n - [deadTreeCount-saveCount - 1]
                        maxLen = Math.max(maxLen, totalTreeCount - deadTreePositionArr[i - 1]);
                    } else{

                        //如果补种中间树
                        //长度  [i+saveCount] - [i-1] -1  下标可以作为长度，因为树下标是连续的，并且从 1 开始
                        maxLen = Math.max(maxLen, deadTreePositionArr[i + saveCount] - deadTreePositionArr[i - 1] - 1);

                    }

                }

                System.out.println(maxLen);

            }


        }catch(Exception e){
            e.printStackTrace();
        }
    }
}
